package leetcode.Hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target的组合。
 * candidates中的每个数字在每个组合中只能使用一次。
 * 注意：解集不能包含重复的组合。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/2/21 18:31
 */
// todo
public class combinationSum2 {
    public static void main(String[] args) {
        combinationSum2(new int[]{2,1,2,5,2}, 5);
    }

    // 结果集合
    static List<List<Integer>> resultList = new ArrayList<>();

    // 1 <= candidates.length <= 100
    // 1 <= candidates[i] <= 50
    // 1 <= target <= 30
    // [1, 2] 3
    // 思路：排序，遇到相同的 continue，前面的数字不能被二次使用
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int i = 0; i < candidates.length; i++) {
            if (i - 1 >= 0 && candidates[i] == candidates[i - 1]) continue;
            else {
                List<Integer> candidateList = new ArrayList<>();
                candidateList.add(candidates[i]);
                backTrack(candidates, target - candidates[i], candidateList, i + 1);
            }
        }
        return resultList;
    }

    static void backTrack(int[] candidates, int remains, List<Integer> candidateList, int begin) {
        if (remains == 0) {
            resultList.add(new ArrayList<>(candidateList));
        } else if (remains < 0 || begin == candidates.length) {
            return;
        } else {
            for (int i = begin; i < candidates.length; i++) {
               
                candidateList.add(candidates[i]);
                backTrack(candidates, remains - candidates[i], candidateList, i + 1);
                candidateList.remove(candidateList.size() - 1);
            }
        }
    }

    // 01背包问题
}
